<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3537：[Usaco2014 Open]Code Breaking </title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2014 Open]Code Breaking </a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2014 Open]Code Breaking </span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Usaco2014 Open]Code Breaking                 </h1>
                <p>时间限制：10s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p><span style="font-size: medium">&nbsp;The cows keep getting in trouble by taking rides on Farmer John's tractor, so he has hidden the keys to the tractor in a fancy new safe in his office. Undeterred, the cows have vowed to try and break into this safe. The safe is protected by a rather complicated passcode system. The passcode entry system is arranged as a rooted tree of N (1 &lt;= N &lt;= 20,000) nodes, each of which requires a digit between 0 and 9. The nodes are indexed 0..N-1. The only information that the cows have is that certain sequences of length 5 do not occur along particular paths upwards through the tree. For instance, suppose the tree is the following (rooted at A):&nbsp;</span></p>
<p><span style="font-size: medium"><img height="106" width="208" alt="" src="../file/3537_0.jpg" /></span></p>
<p><span style="font-size: medium">&nbsp;The cows might know that the sequence 01234 does not occur starting at F, and that the sequence 91234 does not occur starting at E. This information rules out 19 possible passcodes: all those of the form </span></p>
<p><span style="font-size: medium"><img height="106" width="208" alt="" src="../file/3537_1.jpg" /></span></p>
<p><span style="font-size: medium">or</span></p>
<p><span style="font-size: medium">&nbsp;<img height="106" width="208" alt="" src="../file/3537_2.jpg" /></span></p>
<p><span style="font-size: medium"> which gives 19 once we account for the fact that </span></p>
<p><span style="font-size: medium"><img height="106" width="208" alt="" src="../file/3537_3.jpg" /></span></p>
<p><span style="font-size: medium">appears twice. Given M (1 &lt;= M &lt;= 50,000) length-5 sequences, together with their starting nodes in the tree, help the cows figure out how many passcodes have been ruled out. You should compute your answer modulo 1234567. </span></p>
<p></p>
<p></p>
<p></p>
<p></p>
<div><span style="font-size: medium"><span style="background: white; color: black">有一棵N</span><span style="background: white; color: black">个节点的有根树</span><span style="background: white; color: black">,</span><span style="background: white; color: black">每个节点可以填0~9.</span></span></div>
<div><span style="font-size: medium"><span style="background: white; color: black">有M</span><span style="background: white; color: black">个事实</span><span style="background: white; color: black">,</span><span style="background: white; color: black">就是从</span><span style="background: white; color: black">X</span><span style="background: white; color: black">开始往祖先一直跑的的包含</span><span style="background: white; color: black">X</span><span style="background: white; color: black">的</span><span style="background: white; color: black">5</span><span style="background: white; color: black">个节点</span><span style="background: white; color: black">(</span><span style="background: white; color: black">保证</span><span style="background: white; color: black">X</span><span style="background: white; color: black">上面一定存在这样一条路径</span><span style="background: white; color: black">,</span><span style="background: white; color: black">也就是说</span><span style="background: white; color: black">X</span><span style="background: white; color: black">的深度至少为</span><span style="background: white; color: black">5),</span><span style="background: white; color: black">一定不是ABCDE.(0&lt;=A,B,C,D,E&lt;=9)</span></span></div>
<div><span style="font-size: medium"><span style="background: white; color: black">求,</span><span style="background: white; color: black">根据这</span><span style="background: white; color: black">M</span><span style="background: white; color: black">个事实</span><span style="background: white; color: black">,</span><span style="background: white; color: black">共有多少种给这棵树全部填上数的方案一定是不可能的.</span></span></div>
<p></p></p><hr/><h3>输入格式</h3><p><p><font size="4">* Line 1: Two space-separated integers, N and M.</font></p>
<p><font size="4">&nbsp;* Lines 2..N: Line i+1 contains a single integer p(i), denoting the parent of node i in the tree (0 &lt;= p(i) &lt; i). </font></p>
<p><font size="4">* Lines N+1..N+M: Line N+i describes the ith sequence known not to occur in the code. The line will contain v(i) and s(i) separated by a space, where v(i) is the starting node of the sequence, and s(i) is a 5-digit string known not to occur starting at v(i) and proceeding upward in the tree. It is guaranteed that the root is at least 4 steps upward from v(i).</font></p></p><hr/><h3>输出格式</h3><p><p><font size="4">* Line 1: A single integer giving the number of ruled-out configurations, modulo 1234567. </font></p></p><hr/><h3>样例输入</h3><pre>6 2
0
1
2
3
3
4 01234
5 91234
</pre><hr/><h3>样例输出</h3><pre>19 </pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>Gold By liyizhen2</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3537" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3537" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>